class Solution:
    def maxSubArray(self, nums):
        for i in range(1, len(nums)):
            nums[i] = max(nums[i], nums[i]+nums[i-1])
        return max(nums)

if __name__ == '__main__':
    s = Solution()
    L = [0]
    L = [-1, 0]
    L = [-1, 0, 1]
    L = [-1, -2, -3]
    L = [-1, -2, -1, -1, -3, -4]
    # L = [-2,1,-3,4,-1,2,1,-5,7]
    result = s.maxSubArray(L)
    print(result)